#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> result;
        if(nums.size() < 3)
        {
            return result;
        }
        sort(nums.begin(), nums.end());
        if(nums[0] > 0)
        {
            return result;
        }
        for(int i = 0; i < nums.size() - 2; i++)
        {
            if(i != 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0)
                {
                    while(right != 0 && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    right--;
                }
                else if (sum < 0)
                {
                    while(left != nums.size() - 1 && nums[left] == nums[left + 1])
                    {
                        left++;
                    }
                    left++;
                }
                else
                {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while(right != 0 && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    while(left != nums.size() - 1 && nums[left] == nums[left + 1])
                    {
                        left++;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
};

// 辅助函数：打印结果
void printResult(const vector<vector<int>>& result) 
{
    cout << "[";
    for(int i = 0; i < result.size(); i++) 
    {
        cout << "[";
        for(int j = 0; j < result[i].size(); j++) 
        {
            cout << result[i][j];
            if(j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if(i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [-1,0,1,2,-1,-4]
    cout << "测试案例1:" << endl;
    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    cout << "输入: [-1,0,1,2,-1,-4]" << endl;
    vector<vector<int>> result1 = solution.threeSum(nums1);
    cout << "输出: ";
    printResult(result1);
    cout << "期望: [[-1,-1,2],[-1,0,1]]" << endl << endl;
    
    // 测试案例2: [0,1,1]
    cout << "测试案例2:" << endl;
    vector<int> nums2 = {0, 1, 1};
    cout << "输入: [0,1,1]" << endl;
    vector<vector<int>> result2 = solution.threeSum(nums2);
    cout << "输出: ";
    printResult(result2);
    cout << "期望: []" << endl << endl;
    
    // 测试案例3: [0,0,0]
    cout << "测试案例3:" << endl;
    vector<int> nums3 = {0, 0, 0};
    cout << "输入: [0,0,0]" << endl;
    vector<vector<int>> result3 = solution.threeSum(nums3);
    cout << "输出: ";
    printResult(result3);
    cout << "期望: [[0,0,0]]" << endl << endl;
    
    // 测试案例4: 少于3个元素
    cout << "测试案例4 (少于3个元素):" << endl;
    vector<int> nums4 = {1, 2};
    cout << "输入: [1,2]" << endl;
    vector<vector<int>> result4 = solution.threeSum(nums4);
    cout << "输出: ";
    printResult(result4);
    cout << "期望: []" << endl << endl;
    
    // 测试案例5: 全正数
    cout << "测试案例5 (全正数):" << endl;
    vector<int> nums5 = {1, 2, 3, 4, 5};
    cout << "输入: [1,2,3,4,5]" << endl;
    vector<vector<int>> result5 = solution.threeSum(nums5);
    cout << "输出: ";
    printResult(result5);
    cout << "期望: []" << endl << endl;
    
    // 测试案例6: 全负数
    cout << "测试案例6 (全负数):" << endl;
    vector<int> nums6 = {-1, -2, -3, -4, -5};
    cout << "输入: [-1,-2,-3,-4,-5]" << endl;
    vector<vector<int>> result6 = solution.threeSum(nums6);
    cout << "输出: ";
    printResult(result6);
    cout << "期望: []" << endl << endl;
    
    // 测试案例7: 包含重复元素
    cout << "测试案例7 (包含重复元素):" << endl;
    vector<int> nums7 = {-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
    cout << "输入: [-1,0,1,2,-1,-4,-2,-3,3,0,4]" << endl;
    vector<vector<int>> result7 = solution.threeSum(nums7);
    cout << "输出: ";
    printResult(result7);
    cout << "期望: [[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]" << endl << endl;
    
    // 测试案例8: 单个解
    cout << "测试案例8 (单个解):" << endl;
    vector<int> nums8 = {-2, 0, 1, 1, 2};
    cout << "输入: [-2,0,1,1,2]" << endl;
    vector<vector<int>> result8 = solution.threeSum(nums8);
    cout << "输出: ";
    printResult(result8);
    cout << "期望: [[-2,0,2],[-2,1,1]]" << endl << endl;
    
    // 测试案例9: 空数组
    cout << "测试案例9 (空数组):" << endl;
    vector<int> nums9 = {};
    cout << "输入: []" << endl;
    vector<vector<int>> result9 = solution.threeSum(nums9);
    cout << "输出: ";
    printResult(result9);
    cout << "期望: []" << endl << endl;
    
    return 0;
}